{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Speed to Arrive on Time"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minSpeedOnTime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #准时到达的列车最小时速"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个浮点数 <code>hour</code> ，表示你到达办公室可用的总通勤时间。要到达办公室，你必须按给定次序乘坐 <code>n</code> 趟列车。另给你一个长度为 <code>n</code> 的整数数组 <code>dist</code> ，其中 <code>dist[i]</code> 表示第 <code>i</code> 趟列车的行驶距离（单位是千米）。</p>\n",
    "\n",
    "<p>每趟列车均只能在整点发车，所以你可能需要在两趟列车之间等待一段时间。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，第 <code>1</code> 趟列车需要 <code>1.5</code> 小时，那你必须再等待 <code>0.5</code> 小时，搭乘在第 2 小时发车的第 <code>2</code> 趟列车。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回能满足你准时到达办公室所要求全部列车的<strong> 最小正整数 </strong>时速（单位：千米每小时），如果无法准时到达，则返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p>生成的测试用例保证答案不超过 <code>10<sup>7</sup></code> ，且 <code>hour</code> 的 <strong>小数点后最多存在两位数字</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>dist = [1,3,2], hour = 6\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>速度为 1 时：\n",
    "- 第 1 趟列车运行需要 1/1 = 1 小时。\n",
    "- 由于是在整数时间到达，可以立即换乘在第 1 小时发车的列车。第 2 趟列车运行需要 3/1 = 3 小时。\n",
    "- 由于是在整数时间到达，可以立即换乘在第 4 小时发车的列车。第 3 趟列车运行需要 2/1 = 2 小时。\n",
    "- 你将会恰好在第 6 小时到达。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>dist = [1,3,2], hour = 2.7\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>速度为 3 时：\n",
    "- 第 1 趟列车运行需要 1/3 = 0.33333 小时。\n",
    "- 由于不是在整数时间到达，故需要等待至第 1 小时才能搭乘列车。第 2 趟列车运行需要 3/3 = 1 小时。\n",
    "- 由于是在整数时间到达，可以立即换乘在第 2 小时发车的列车。第 3 趟列车运行需要 2/3 = 0.66667 小时。\n",
    "- 你将会在第 2.66667 小时到达。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>dist = [1,3,2], hour = 1.9\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>不可能准时到达，因为第 3 趟列车最早是在第 2 小时发车。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == dist.length</code></li>\n",
    "\t<li><code>1 <= n <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= dist[i] <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= hour <= 10<sup>9</sup></code></li>\n",
    "\t<li><code>hours</code> 中，小数点后最多存在两位数字</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-speed-to-arrive-on-time](https://leetcode.cn/problems/minimum-speed-to-arrive-on-time/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-speed-to-arrive-on-time](https://leetcode.cn/problems/minimum-speed-to-arrive-on-time/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,2]\\n6', '[1,3,2]\\n2.7', '[1,3,2]\\n1.9']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "\n",
    "        def check(target):\n",
    "            sum_=0\n",
    "            for i in dist[:-1]:\n",
    "                sum_+=i//target\n",
    "                if i%target!=0:\n",
    "                    sum_+=1\n",
    "            sum_+=dist[-1]/target\n",
    "            return sum_\n",
    "        \n",
    "        left=1\n",
    "        right=int(1e7)\n",
    "\n",
    "        while left<=right:\n",
    "            mid=left+int((right-left)/2)\n",
    "            if check(mid)>hour:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid-1\n",
    "        \n",
    "        if left>int(1e7):\n",
    "            return -1\n",
    "        else:\n",
    "            return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        n = len(dist)\n",
    "        hr = round(hour * 100)\n",
    "        # 时间必须要大于路程段数减 1\n",
    "        if hr <= 100 * (n - 1):\n",
    "            return -1\n",
    "        # 判断当前时速是否满足时限\n",
    "        def check(speed: int) -> bool:\n",
    "            t = 0\n",
    "            # 前 n-1 段中第 i 段贡献的时间： floor(dist[i] / mid)\n",
    "            for i in range(n - 1):\n",
    "                t += (dist[i] - 1) // speed + 1\n",
    "            # 最后一段贡献的时间： dist[n-1] / mid\n",
    "            t *= speed\n",
    "            t += dist[-1]\n",
    "            return t * 100 <= hr * speed   # 通分以转化为整数比较\n",
    "        \n",
    "        # 二分\n",
    "        l, r = 1, 10 ** 7\n",
    "        while l < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l   # 满足条件的最小时速"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        check = lambda speed: sum(ceil(d / speed) for d in dist[:-1]) + dist[-1] / speed <= hour\n",
    "        return bisect_left(range(1, int(sum(dist) / (hour - len(dist) + 1)) + 2), 1, key=check) + 1 if hour > len(dist) - 1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        if hour<=len(dist)-1:\n",
    "            return -1\n",
    "        left=1\n",
    "        right=10**7\n",
    "        while left<right:\n",
    "            mid=(left+right)//2\n",
    "            tmp=sum(math.ceil(x/mid) for x in dist[:-1])+dist[-1]/mid\n",
    "            if tmp>hour:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        n=len(dist)\n",
    "        l,r=1,10**7\n",
    "        ans=-1\n",
    "        while l<=r:\n",
    "            x=0\n",
    "            m=l+(r-l)//2\n",
    "            for i,t in enumerate(dist):\n",
    "                if i!=n-1:\n",
    "                    x+=(t+m-1)//m  #上取整\n",
    "                else:\n",
    "                    x+=t/m\n",
    "            if x>hour:\n",
    "                l=m+1\n",
    "            else:\n",
    "                ans=m\n",
    "                r=m-1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], h: float) -> int:\n",
    "        l,r=1,10**7+1\n",
    "        def is_valid(mid,h):\n",
    "            c=0      \n",
    "            for i in dist[:-1]:\n",
    "                t =1 if i%mid!=0 else 0\n",
    "                c=c+t+i//mid\n",
    "            c=c+dist[-1]/mid\n",
    "            print(mid,h,c,bool(c>=h))\n",
    "            return c>h\n",
    "        t=1\n",
    "        while l<r:\n",
    "            t+=1\n",
    "            mid=(l+r)//2\n",
    "            if is_valid(mid,h):\n",
    "                l=mid+1\n",
    "            else:\n",
    "                r=mid\n",
    "        print(l,r)\n",
    "        if l==10**7+1 and is_valid(l,h):\n",
    "            return -1\n",
    "        return l%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        left = 0\n",
    "        right = 10**8  # int(max(dist) * len(dist) ) +1\n",
    "        total = 0\n",
    "        lower = 0\n",
    "        while left + 1 < right:\n",
    "            m = (left+right)//2\n",
    "            cnt =0\n",
    "            for i in range(len(dist)):\n",
    "                if i < len(dist)-1:\n",
    "                    cnt+=dist[i]//m + min(dist[i] % m,1)\n",
    "                else:\n",
    "                    cnt+= dist[i]/m\n",
    "            print(cnt,m,right,left)\n",
    "            if cnt>hour:\n",
    "                left = m\n",
    "            else:\n",
    "                lower+=1\n",
    "                right = m\n",
    "            total+=1\n",
    "        if lower==0:\n",
    "            return  -1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_hour(self, dist, mid):\n",
    "        return sum(ceil(d / mid) for d in dist[:-1]) + dist[-1] / mid\n",
    "\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        left, right = 1, 10**9    # 左闭右开，表示速度\n",
    "        if len(dist)-1 >= hour:\n",
    "            return -1\n",
    "        while(left < right):\n",
    "            mid = (left + right) >> 1\n",
    "            if self.get_hour(dist, mid) > hour:     # 花费时间太多，速度太慢，left要右移\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        n = len(dist)\n",
    "\n",
    "        # def check(velocity: int) -> bool:\n",
    "        #     return \n",
    "\n",
    "        # Lower bound.\n",
    "        left, right = 1, max(dist) * 100\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if sum([math.ceil(x / mid) for x in dist[:-1]]) + dist[-1] / mid <= hour:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left if sum([math.ceil(x / left) for x in dist[:-1]]) + dist[-1] / left <= hour else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        n = len(dist)\n",
    "        def check(v):\n",
    "            sump = 0\n",
    "            for i in range(n-1):\n",
    "                sump += math.ceil(dist[i]/v)\n",
    "            sump += dist[n-1]/v\n",
    "            return sump>hour\n",
    "        if hour <= n - 1:\n",
    "            return -1\n",
    "        left = 1\n",
    "        right = (10**7)\n",
    "        while left<=right:\n",
    "            mid = (left+right)//2\n",
    "            if check(mid):\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid-1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        l, r = 1, 10 ** 7\n",
    "        def check(n):\n",
    "            ans = 0\n",
    "            for i, x in enumerate(dist):\n",
    "                if i != len(dist) - 1:\n",
    "                    ans += ceil(x / n)\n",
    "                else:\n",
    "                    ans += x / n\n",
    "            return ans <= hour\n",
    "        while l < r:\n",
    "            mid = l + r  >> 1\n",
    "            if check(mid):\n",
    "                r = mid \n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l if check(l) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def check)\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        def check(speed:int):\n",
    "            if speed==0:\n",
    "                return False\n",
    "            ans=0\n",
    "            for dis in dist:\n",
    "                time_=dis/speed\n",
    "                # print(time_,dis,dis/speed)\n",
    "                if ans+time_>hour:\n",
    "                    return False\n",
    "                if time_%1!=0:\n",
    "                    time_=int(time_)+1\n",
    "                ans=ans+time_\n",
    "\n",
    "                # print(time_,speed,\"ans\",ans)\n",
    "                \n",
    "            return True\n",
    "        ll,rr=1,10**7\n",
    "        while ll<=rr:\n",
    "            mid=ll+(rr-ll)//2\n",
    "            isOk=check(mid)\n",
    "            if isOk:# 速度可以\n",
    "                rr=mid-1\n",
    "            else:# 速度不行 # 加速\n",
    "                ll=mid+1\n",
    "        if ll==10**7+1:\n",
    "            return -1\n",
    "        if check(ll):\n",
    "            # print(ll,rr,check(ll),check(rr))\n",
    "            return ll\n",
    "        else:\n",
    "            return -1\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        n = len(dist)\n",
    "        hour = round(hour*100)\n",
    "\n",
    "        if hour <= 100*(n - 1): return -1\n",
    "\n",
    "        def check(speed):\n",
    "            t = 0\n",
    "            for i in range(n-1):\n",
    "                t += (dist[i] - 1)//speed + 1\n",
    "            \n",
    "            t *= speed\n",
    "            t += dist[-1]\n",
    "            return t * 100 <= hour * speed\n",
    "        \n",
    "        left, right = 1, 10**7\n",
    "        while left < right:\n",
    "            mid = left + (right - left)//2\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist, hour):\n",
    "        l = 1\n",
    "        r = 10**7 + 1\n",
    "        n = len(dist)\n",
    "        while l<r:\n",
    "            mid = (l + r) // 2\n",
    "            tmp = 0\n",
    "            for i in range(n - 1):\n",
    "                tmp += (dist[i] + mid - 1) // mid\n",
    "                # print(l, r, mid, i, tmp)\n",
    "            tmp += dist[-1] / mid\n",
    "            # print(tmp)\n",
    "            if tmp <= hour:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l if l <= 10**7 else -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        n = len(dist)\n",
    "        # hr = round(hour * 100)\n",
    "        # 时间必须要大于路程段数减 1\n",
    "        if hour <= (n - 1):\n",
    "            return -1\n",
    "        # 判断当前时速是否满足时限\n",
    "        def check(speed: int) -> bool:\n",
    "            t = 0\n",
    "            # 前 n-1 段中第 i 段贡献的时间： floor(dist[i] / mid)\n",
    "            for i in range(n - 1):\n",
    "                t += (dist[i] - 1) // speed + 1\n",
    "            # 最后一段贡献的时间： dist[n-1] / mid\n",
    "            t *= speed\n",
    "            t += dist[-1]\n",
    "            return t * 100 <= round(hour * 100) * speed   # 通分以转化为整数比较\n",
    "        \n",
    "        # 二分\n",
    "        l, r = 1, 10 ** 7\n",
    "        while l < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l   # 满足条件的最小时速\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        lo, hi = 1, max(dist)+1\n",
    "        if t := hour-int(hour):\n",
    "            hi = max(hi, int(dist[-1]/t)+2)\n",
    "        s = hi\n",
    "        while lo < hi:\n",
    "            mid = (lo + hi) // 2\n",
    "            t = sum((d - 1) // mid + 1 for d in dist[:-1])\n",
    "            t += dist[-1] / mid\n",
    "            if t <= hour: hi = mid\n",
    "            else: lo = mid + 1\n",
    "        return hi if hi < s else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        n = len(dist)\n",
    "        hr = round(hour * 100)\n",
    "        # 时间必须要大于路程段数减 1\n",
    "        if hr <= 100 * (n - 1):\n",
    "            return -1\n",
    "        # 判断当前时速是否满足时限\n",
    "        def check(speed: int) -> bool:\n",
    "            t = 0\n",
    "            # 前 n-1 段中第 i 段贡献的时间： floor(dist[i] / mid)\n",
    "            for i in range(n - 1):\n",
    "                t += (dist[i] - 1) // speed + 1\n",
    "            # 最后一段贡献的时间： dist[n-1] / mid\n",
    "            t *= speed\n",
    "            t += dist[-1]\n",
    "            return t * 100 <= hr * speed   # 通分以转化为整数比较\n",
    "        \n",
    "        # 二分\n",
    "        l, r = 1, 10 ** 7\n",
    "        while l < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l   # 满足条件的最小时速\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        # hour的小数是怎么来的？因为前n-1次列车都是整点出发，所以小数是通过最后一趟列车来的！所以二分只循环计算前n-1，最后一次直接除保留小数。\n",
    "        # 由于题目说了，hour小数最多存在两位，也就是最快0.01，那么右端点只需设置max(dist) * 100就能满足题意。\n",
    "        if hour < len(dist) -1:\n",
    "            return -1\n",
    "        start, end = 1, max(dist)*100\n",
    "\n",
    "        def cal_time(speed):\n",
    "            count = 0\n",
    "            for num in dist[:-1]:\n",
    "                if num % speed == 0: # super important. % speed //speed ...not 2\n",
    "                    count += num//speed\n",
    "                else:\n",
    "                    count += num//speed + 1\n",
    "            # 单独计算最后一次的耗时\n",
    "            count += dist[-1]/speed\n",
    "            # print(speed, count)\n",
    "            return count\n",
    "        while start + 1 < end:\n",
    "            mid = (start + end)//2 # don't forget //2\n",
    "            print(mid, cal_time(mid))\n",
    "            if cal_time(mid) >= hour: # more than than hour need larger speed\n",
    "                start = mid \n",
    "            else:\n",
    "                end = mid\n",
    "\n",
    "        if cal_time(start) <= hour: # <= not >=\n",
    "            return start\n",
    "        elif cal_time(end) <= hour:\n",
    "            return end\n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "# https://leetcode.cn/problems/minimum-speed-to-arrive-on-time/solutions/792213/5764zhun-shi-dao-da-de-lie-che-zui-xiao-phes3/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        n = len(dist)\n",
    "        hr = round(hour * 100)\n",
    "        # 时间必须要大于路程段数减 1\n",
    "        if hr <= 100 * (n - 1):\n",
    "            return -1\n",
    "        # 判断当前时速是否满足时限\n",
    "        def check(speed: int) -> bool:\n",
    "            t = 0\n",
    "            # 前 n-1 段中第 i 段贡献的时间： floor(dist[i] / mid)\n",
    "            for i in range(n - 1):\n",
    "                t += (dist[i] - 1) // speed + 1\n",
    "            # 最后一段贡献的时间： dist[n-1] / mid\n",
    "            t *= speed\n",
    "            t += dist[-1]\n",
    "            return t * 100 <= hr * speed   # 通分以转化为整数比较\n",
    "        \n",
    "        # 二分\n",
    "        l, r = 1, 10 ** 7\n",
    "        while l <= r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                r = mid-1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l   # 满足条件的最小时速\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        n = len(dist)\n",
    "        hr = round(hour * 100)\n",
    "        # 时间必须要大于路程段数减 1\n",
    "        if hr <= 100 * (n - 1):\n",
    "            return -1\n",
    "        # 判断当前时速是否满足时限\n",
    "        def check(speed: int) -> bool:\n",
    "            t = 0\n",
    "            # 前 n-1 段中第 i 段贡献的时间： floor(dist[i] / mid)\n",
    "            for i in range(n - 1):\n",
    "                t += (dist[i] - 1) // speed + 1\n",
    "            # 最后一段贡献的时间： dist[n-1] / mid\n",
    "            t *= speed\n",
    "            t += dist[-1]\n",
    "            return t * 100 <= hr * speed   # 通分以转化为整数比较\n",
    "        \n",
    "        # 二分\n",
    "        l, r = 1, 10 ** 7\n",
    "        while l < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l   # 满足条件的最小时速\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        n = len(dist)\n",
    "\n",
    "        def check(velocity: int) -> bool:\n",
    "            total = 0.0\n",
    "            for i in range(n - 1):\n",
    "                total += math.ceil(dist[i] / velocity)\n",
    "                if total > hour:\n",
    "                    return False\n",
    "            return total + dist[-1] / velocity <= hour\n",
    "\n",
    "        # Lower bound.\n",
    "        left, right = 1, 10**7\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left if check(left) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        n = len(dist)\n",
    "        hr = round(hour * 100)\n",
    "        # 时间必须要大于路程段数减 1\n",
    "        if hr <= 100 * (n - 1):\n",
    "            return -1\n",
    "        # 判断当前时速是否满足时限\n",
    "        def check(speed: int) -> bool:\n",
    "            t = 0\n",
    "            # 前 n-1 段中第 i 段贡献的时间： floor(dist[i] / mid)\n",
    "            for i in range(n - 1):\n",
    "                t += math.ceil(dist[i]/speed)\n",
    "            # 最后一段贡献的时间： dist[n-1] / mid\n",
    "            t *= speed\n",
    "            t += dist[-1]\n",
    "            return t * 100 <= hr * speed   # 通分以转化为整数比较\n",
    "        \n",
    "        # 二分\n",
    "        l, r = 1, 10 ** 7\n",
    "        while l <= r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                r = mid-1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l   # 满足条件的最小时速\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import math\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        def check(speed):\n",
    "            res = 0\n",
    "            for i in range(len(dist)):\n",
    "                if i < len(dist) - 1:\n",
    "                    res += math.ceil(dist[i] / speed)\n",
    "                else:\n",
    "                    res += dist[i] / speed\n",
    "\n",
    "            return res <= hour\n",
    "\n",
    "        left, right = 1, 10 ** 7 + 1\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right - 1) // 2\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        return -1 if left == 10 ** 7 + 1 else left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        n = len(dist)\n",
    "\n",
    "        def check(velocity: int) -> bool:\n",
    "            total = 0.0\n",
    "            for i in range(n - 1):\n",
    "                total += math.ceil(dist[i] / velocity)\n",
    "            return total + dist[-1] / velocity <= hour\n",
    "\n",
    "        # Lower bound.\n",
    "        left, right = 1, 10**7\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left if check(left) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        n = len(dist)\n",
    "\n",
    "        def check(velocity: int) -> bool:\n",
    "            total = 0.0\n",
    "            for i in range(n - 1):\n",
    "                total += math.ceil(dist[i] / velocity)\n",
    "            return total + dist[-1] / velocity <= hour\n",
    "\n",
    "        # Lower bound.\n",
    "        left, right = 1, 10**9\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left if check(left) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        # guess speed\n",
    "        if hour <= len(dist)-1:\n",
    "            return -1 # impossible\n",
    "        left,right = 1,max(max(dist),math.ceil(dist[-1]/(hour-len(dist)+1)))\n",
    "        while left < right:\n",
    "            mid = left + (right-left)//2\n",
    "            if self.total_hour(mid,dist) <= hour:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid+1\n",
    "            \n",
    "        return right\n",
    "        \n",
    "\n",
    "    \n",
    "\n",
    "    def total_hour(self,speed,dist):\n",
    "        res = 0\n",
    "        for i,d in enumerate(dist):\n",
    "            if i == len(dist)-1:\n",
    "                res += d/speed\n",
    "                break\n",
    "            elif d > speed:\n",
    "                res += d//speed + 1 if d%speed else d//speed\n",
    "            else:\n",
    "                res += 1\n",
    "        return res\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        def check(x):\n",
    "            return sum((ele + x - 1) //x for ele in dist[:-1] ) + dist[-1]/x <= hour\n",
    "        idx = bisect_left(range(1, 10**9 + 1), 1, key=check) + 1 \n",
    "        if idx == 10**9 + 1:\n",
    "            return -1\n",
    "        return idx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        l, r = 1, 10**7\n",
    "        n = len(dist)\n",
    "        while l < r:\n",
    "            mid = (l+r) >> 1\n",
    "            if sum([math.ceil(dist[i]/mid) for i in range(n-1)]) + dist[-1]/mid > hour:\n",
    "                l = mid+1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l if sum([math.ceil(dist[i]/l) for i in range(n-1)]) + dist[-1]/l <= hour else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        if len(dist) - 1 >= hour:\n",
    "            return -1\n",
    "\n",
    "        def check(speed):\n",
    "            time = sum([math.ceil(d / speed) for d in dist[:-1]])\n",
    "            time += dist[-1] / speed\n",
    "            return time <= hour\n",
    "        left, right = 1, int(1e7)\n",
    "        while left < right:\n",
    "            mid = (left + right) >> 1\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        n = len(dist)\n",
    "        hr = round(hour * 100)\n",
    "        # 时间必须要大于路程段数减 1\n",
    "        if hr <= 100 * (n - 1):\n",
    "            return -1\n",
    "\n",
    "        # 判断当前时速是否满足时限\n",
    "        # 二分\n",
    "        l, r = 1, 10 ** 7\n",
    "        while l < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            t = 0\n",
    "            # 前 n-1 段中第 i 段贡献的时间： floor(dist[i] / mid)\n",
    "            for i in range(n - 1):\n",
    "                t += (dist[i] - 1) // mid + 1\n",
    "            # 最后一段贡献的时间： dist[n-1] / mid\n",
    "            t *= mid\n",
    "            t += dist[-1]\n",
    "            if  t * 100 <= hr * mid:  # 通分以转化为整数比较\n",
    "\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l  # 满足条件的最小时速\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        hourLeft = hour - len(dist) + 1\n",
    "        def hourUseBeforeLast(v, nums = dist[0:-1]):\n",
    "            hourUse = 0\n",
    "            for item in nums:\n",
    "                temp = item // v\n",
    "                tempHour = temp if temp * v == item else temp + 1\n",
    "                hourUse += tempHour\n",
    "            return hourUse\n",
    "        \n",
    "        if hourLeft <= 0:\n",
    "            return -1\n",
    "        else:\n",
    "            vMax = max(dist) * 100\n",
    "            vMin = 1\n",
    "            while vMin < vMax:\n",
    "                vMid = (vMin + vMax) // 2\n",
    "                if hourUseBeforeLast(vMid) + dist[-1] / vMid <= hour:\n",
    "                    vMax = vMid\n",
    "                else:\n",
    "                    vMin = vMid + 1\n",
    "            return vMin"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# import math\r\n",
    "class Solution:\r\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\r\n",
    "        # if len(dist)-1>=hour:\r\n",
    "        #     return -1\r\n",
    "\r\n",
    "        def check(dist,speed,hour):\r\n",
    "            res=0\r\n",
    "            for ind,per in enumerate(dist):\r\n",
    "                spend=per*1.0/speed\r\n",
    "                res+=spend if ind == len(dist)-1 else math.ceil(spend)\r\n",
    "            return res<=hour\r\n",
    "\r\n",
    "        left=1\r\n",
    "        right=10000000\r\n",
    "        while left <right:\r\n",
    "            mid=(left+right)>>1\r\n",
    "            if check(dist,mid,hour):\r\n",
    "                right=mid\r\n",
    "            else:\r\n",
    "                left=mid+1\r\n",
    "\r\n",
    "        return left if check(dist,left,hour) else -1\r\n",
    "\r\n",
    "        \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        if hour <= len(dist) - 1:\n",
    "            return -1\n",
    "        left, right = 1, ceil(max(max(dist), dist[-1] / (hour + 1 - len(dist))) if hour <= len(dist) else max(dist))\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            time = sum((x - 1) // mid + 1 for x in dist[:-1]) + dist[-1] / mid\n",
    "            if time > hour:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        n = len(dist)\n",
    "        if hour <= n - 1:\n",
    "            return -1\n",
    "        left = 1\n",
    "        right = 10e7\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if sum([(dist[i] + mid - 1) // mid for i in range(n - 1)]) + dist[-1] / mid > hour:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return round(left)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        check = lambda speed: sum(ceil(d / speed) for d in dist[:-1]) + dist[-1] / speed <= hour\n",
    "        return bisect_left(range(1, int(sum(dist) / (hour - len(dist) + 1)) + 2), 1, key=check) + 1 if hour > len(dist) - 1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "\n",
    "        def check(target):\n",
    "            sum_=0\n",
    "            for i in dist[:-1]:\n",
    "                sum_+=(i-1)//target+1\n",
    "            sum_+=dist[-1]/target\n",
    "            return sum_\n",
    "        \n",
    "        left=1\n",
    "        right=max(dist)*100\n",
    "\n",
    "        while left<=right:\n",
    "            mid=left+int((right-left)/2)\n",
    "            if check(mid)>hour:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid-1\n",
    "        \n",
    "        if left>max(dist)*100:\n",
    "            return -1\n",
    "        else:\n",
    "            return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist, hour):\n",
    "        # 如果时间小于dist -1返回 -1\n",
    "        if hour  <= len(dist) - 1:\n",
    "            return -1\n",
    "        # 设置二分查找边界\n",
    "        left,right = 1, max(dist) * 100\n",
    "        while left < right:\n",
    "            cost, mid = 0, (left + right) // 2\n",
    "            for i in dist[:-1]:\n",
    "                cost += (i + mid - 1) // mid\n",
    "                # 如果cost已经大于hour，直接left移位，重新计算\n",
    "                if cost > hour:\n",
    "                    left = mid + 1\n",
    "                    continue\n",
    "            # 单独计算最后一次的耗时\n",
    "            cost += dist[-1] / mid\n",
    "            if cost > hour:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return -1 if left == 10 ** 9 else left\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        left, right = 1, 10000000\n",
    "        l = len(dist)\n",
    "        while left <right:\n",
    "            mid = left+ (right-left)//2\n",
    "            if float(sum((r+mid-1)//mid for r in dist[:l-1]))+dist[l-1]/mid<=hour:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid +1\n",
    "        return right if float(sum((r+left-1)//left for r in dist[:l-1]))+dist[l-1]/left<=hour else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        left, right = 1, 10000000\n",
    "        l = len(dist)\n",
    "        while left <right:\n",
    "            mid = left+ (right-left)//2\n",
    "            if float(sum((r+mid-1)//mid for r in dist[:l-1]))+dist[l-1]/mid<=hour:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid +1\n",
    "        return right if hour>l-1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        n = len(dist)\n",
    "        if n-1 >= hour:\n",
    "            return -1\n",
    "    \n",
    "        def helper(v):\n",
    "            t = 0\n",
    "            for d in dist[:-1]:\n",
    "                t += (d + v -1) // v\n",
    "            t += dist[-1] / v\n",
    "            return t <= hour\n",
    "\n",
    "        left, right = 1, max(dist)*100\n",
    "        while left < right:\n",
    "            mid = (left + right)//2\n",
    "            if helper(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        n = len(dist)\n",
    "        if n - 1 >= hour:\n",
    "            return -1\n",
    "        def check(x):\n",
    "            res = 0\n",
    "            if x == 0:\n",
    "                return False\n",
    "            for i in dist[:-1]:\n",
    "                res += (i + x - 1) // x\n",
    "            res += dist[-1] / x    \n",
    "            return res <= hour  \n",
    "        down, up = 0,int(1e7) + 1\n",
    "        while down <= up:\n",
    "            mid = down + up >> 1\n",
    "            if check(mid):\n",
    "                up = mid - 1\n",
    "            else:\n",
    "                down = mid + 1          \n",
    "        return down        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist, hour):\n",
    "        # 如果时间小于dist -1返回 -1\n",
    "        if hour  <= len(dist) - 1:\n",
    "            return -1\n",
    "        # 设置二分查找边界\n",
    "        left,right = 1, max(dist) * 100\n",
    "        while left < right:\n",
    "            cost, mid = 0, (left + right) // 2\n",
    "            for i in dist[:-1]:\n",
    "                cost += (i + mid - 1) // mid\n",
    "                # 如果cost已经大于hour，直接left移位，重新计算\n",
    "                if cost > hour:\n",
    "                    left = mid + 1\n",
    "                    continue\n",
    "            # 单独计算最后一次的耗时\n",
    "            cost += dist[-1] / mid\n",
    "            if cost > hour:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return -1 if left == 10 ** 9 else left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        left = 1\n",
    "        right = max(dist) * (10**7) + 1\n",
    "        \n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            total_time = 0\n",
    "\n",
    "            for d in dist[:-1]:\n",
    "                total_time += (d + mid - 1) // mid\n",
    "            \n",
    "            # 计算最后一个距离需要的时间，并判断是否能准时到达\n",
    "            last_dist_time = dist[-1] / mid\n",
    "            if last_dist_time > hour:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                total_time += last_dist_time\n",
    "                if total_time <= hour:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "        \n",
    "        return -1 if left == max(dist) * (10**7) + 1 else left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        left, right = 1, 10000000\n",
    "        l = len(dist)\n",
    "        while left <right:\n",
    "            mid = left+ (right-left)//2\n",
    "            if float(sum((r+mid-1)//mid for r in dist[:l-1]))+dist[l-1]/mid<=hour:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid +1\n",
    "        return right if hour>l-1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        if ceil(hour) < len(dist):\n",
    "            return -1\n",
    "        l, r = 0, int(1e9+1)\n",
    "        while l +1 < r:\n",
    "            mid = l + (r-l) //2\n",
    "            if dist[-1]/mid + sum(ceil(x/mid) for x in dist[:-1]) > hour:\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\r\n",
    "        use_dist = dist[: -1]\r\n",
    "\r\n",
    "        def use_hour(mid):\r\n",
    "            return sum((i-1)//mid+1 for i in use_dist)  # 除法向上取整\r\n",
    "\r\n",
    "        left = 1\r\n",
    "        right = 10**7\r\n",
    "        if len(dist)-1 > hour//1 or len(dist)-1 >= hour:\r\n",
    "            return -1\r\n",
    "\r\n",
    "        while left <= right:  # 区间不为空\r\n",
    "            mid = (left+right) // 2\r\n",
    "            if use_hour(mid)+dist[-1]/mid <= hour:\r\n",
    "                right = mid - 1\r\n",
    "            else:\r\n",
    "                left = mid + 1\r\n",
    "\r\n",
    "        # - 终止: right = left = mid 且必符合条件(判断<=hour)\r\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        if hour <= len(dist) - 1:\n",
    "            return -1\n",
    "        left = 1\n",
    "        right = 10e7\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if sum([(dist[i] + mid - 1) // mid for i in range(len(dist) - 1)]) + dist[len(dist) - 1] / mid > hour:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return int(left)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        n = len(dist) - 1\n",
    "        if hour <= n:\n",
    "            return -1\n",
    "        high = max(*dist, ceil(dist[-1]/(hour-n)))\n",
    "        low = 1\n",
    "        while low < high:\n",
    "            mid = low + high >> 1\n",
    "            if sum(ceil(d/mid) for d in dist) - ceil(dist[-1]/mid) + dist[-1]/mid <=hour:\n",
    "                high=mid\n",
    "            else:\n",
    "                low=mid+1\n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        n = len(dist) - 1\n",
    "        if hour <= n:\n",
    "            return -1\n",
    "        high = max(*dist, ceil(dist[-1]/(hour-n)))\n",
    "        low = 1\n",
    "        while low < high:\n",
    "            mid = low + high >> 1\n",
    "            if sum(ceil(d/mid) for d in dist) - ceil(dist[-1]/mid) + dist[-1]/mid <=hour:\n",
    "                high=mid\n",
    "            else:\n",
    "                low=mid+1\n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        left = 1\n",
    "        right = 10e7\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if sum([(dist[i] + mid - 1) // mid for i in range(len(dist) - 1)]) + dist[len(dist) - 1] / mid > hour:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        if sum([(dist[i] + left - 1) // left for i in range(len(dist) - 1)]) + dist[len(dist) - 1] / left > hour:\n",
    "            return -1\n",
    "        return int(left)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "\n",
    "        if hour  <= len(dist) - 1:\n",
    "            return -1\n",
    "        \n",
    "        left = 1\n",
    "        right = max(dist) * 100\n",
    "        \n",
    "        def check(s: int):\n",
    "            count = 0\n",
    "            for i in dist[:-1]:\n",
    "                count += (i + s - 1) // s\n",
    "                if count > hour:\n",
    "                    return False\n",
    "            count += dist[-1] / s\n",
    "            if count > hour:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (right + left) // 2\n",
    "            if check(mid):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        if hour <= len(dist) - 1:\n",
    "            return -1\n",
    "        return bisect_left(range(1, max(dist) * 101), -hour, key=lambda speed:-sum((d + speed - 1) // speed for d in dist[:-1]) - dist[-1] / speed) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        n = len(dist) - 1\n",
    "        if hour <= n:\n",
    "            return -1\n",
    "        return bisect_left(range(1, max(*dist,ceil(dist[-1]/(hour-n)))), -hour, key=lambda speed:-sum((d + speed - 1) // speed for d in dist[:-1]) - dist[-1] / speed) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        #寻找左边界\n",
    "        n = len(dist)\n",
    "        if hour<=n-1: # 肯定完成不了\n",
    "            return -1\n",
    "        l = 1 #最小正整数\n",
    "        r = max(dist)*100+1\n",
    "        def f(x):\n",
    "            t = 0.00 #浮点数\n",
    "            for i in range(n-1):\n",
    "                t += math.ceil(dist[i]/x)\n",
    "            t += dist[n-1]/x #不保留两位小数，防止四舍五入导致误差\n",
    "            return t\n",
    "        while l<r:\n",
    "            #左闭右开\n",
    "            mid = (l + r) //2\n",
    "            t = f(mid)\n",
    "            if t>hour:\n",
    "                l = mid + 1\n",
    "            elif t <= hour:\n",
    "                r = mid\n",
    "        return l\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\r\n",
    "        use_dist = dist[: -1]\r\n",
    "\r\n",
    "        def use_hour(mid):\r\n",
    "            return sum((i-1)//mid+1 for i in use_dist)  # 除法向上取整\r\n",
    "\r\n",
    "        left = 1\r\n",
    "        right = 10**7\r\n",
    "        if len(dist)-1 > hour//1 or len(dist)-1 >= hour:\r\n",
    "            return -1\r\n",
    "\r\n",
    "        while left <= right:  # 区间不为空\r\n",
    "            mid = (left+right) // 2\r\n",
    "            if use_hour(mid)+dist[-1]/mid <= hour:\r\n",
    "                right = mid - 1\r\n",
    "            else:\r\n",
    "                left = mid + 1\r\n",
    "\r\n",
    "        # - 终止: right = left = mid 且必符合条件\r\n",
    "        # * (因为一定有解, 无解情况排除了)(判断<=hour)\r\n",
    "        # - 此时执行right = mid - 1, 由符合条件变为不符合条件\r\n",
    "        # - 因此right移到红区间边界外, left是最终结果\r\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        if hour <= len(dist)-1:\n",
    "            return -1\n",
    "        def fun(v):\n",
    "            s = 0\n",
    "            for i in dist[:-1]:\n",
    "                s += ceil(i/v)\n",
    "            s += dist[-1]/v\n",
    "            return s <= hour\n",
    "        l, r = 1, max(dist)*100\n",
    "        while l < r:\n",
    "            m = (l + r) // 2\n",
    "            if fun(m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        if hour <= len(dist) - 1:\n",
    "            return -1\n",
    "        left = 1\n",
    "        right = 10e7\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if sum([(dist[i] + mid - 1) // mid for i in range(len(dist) - 1)]) + dist[-1] / mid > hour:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return int(left)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        n = len(dist)\n",
    "        if hour < n - 1:  # 如果hour小于n-1，则无法在给定时间内到达目的地\n",
    "           return -1\n",
    "    \n",
    "        left, right = 1, 10**7\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            timecost = sum(ceil(dis / mid) for dis in dist[:-1])  # 注意使用 ceil 来向上取整\n",
    "            timecost += dist[-1] / mid  # 最后一段路是例外，可以不用整数时间到达\n",
    "\n",
    "            if timecost > hour:  # 如果需要的时间比 hour 更长\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "    # 需要再检查一次，确保结果正确\n",
    "        timecost = sum(ceil(dis / left) for dis in dist[:-1])\n",
    "        timecost += dist[-1] / left\n",
    "        if timecost > hour:\n",
    "            return -1  # 即使使用最大速度，也不能在规定的时间内到达\n",
    "        return left\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        n = len(dist) - 1\n",
    "        if hour <= n:\n",
    "            return -1\n",
    "        high = max(*dist, ceil(dist[-1]/(hour - n)))\n",
    "        low = 1\n",
    "        while low < high:\n",
    "            mid = low + high >> 1\n",
    "            if sum((d + mid - 1) // mid for d in dist) - ceil(dist[-1] / mid) + dist[-1]/mid <= hour:\n",
    "                high=mid\n",
    "            else:\n",
    "                low=mid+1\n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        if hour<=len(dist)-1:\n",
    "            return -1\n",
    "        n=len(dist)\n",
    "        right=max(max(dist),ceil(dist[n-1]/(hour-n+1)))\n",
    "        left=1\n",
    "        while left < right:\n",
    "            mid=(left+right)//2\n",
    "            if(sum(ceil(d/mid)for d in dist)-ceil(dist[n-1]/mid)+dist[n-1]/mid)<=hour:\n",
    "                right=mid\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        n = len(dist) - 1\n",
    "        if hour <= n:\n",
    "            return -1\n",
    "        high = max(*dist, ceil(dist[-1]/(hour - n)))\n",
    "        low = 1\n",
    "        while low < high:\n",
    "            mid = low + high >> 1\n",
    "            if sum(ceil(d / mid) for d in dist) - ceil(dist[-1] / mid) + dist[-1]/mid <= hour:\n",
    "                high=mid\n",
    "            else:\n",
    "                low=mid+1\n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        def check(speed):\n",
    "            res = 0\n",
    "            for i, d in enumerate(dist):\n",
    "                res += (d / speed) if i == len(dist) - 1 else math.ceil(d / speed)\n",
    "            return res <= hour\n",
    "\n",
    "        r = 10**7 + 1\n",
    "        ans = bisect_left(range(1, r), True, key=check) + 1\n",
    "        return -1 if ans == r else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        n = len(dist)\n",
    "        if n - 1 >= hour:\n",
    "            return -1\n",
    "\n",
    "        def cal(x, y):\n",
    "            return x if x % y == 0 else y * (x // y + 1)\n",
    "\n",
    "        hour = round(hour * 100)\n",
    "        def check(mid):\n",
    "            res = dist[-1]\n",
    "            for i in range(n - 1):\n",
    "                res += cal(dist[i], mid)\n",
    "                \n",
    "            return res * 100 <= hour * mid\n",
    "\n",
    "        l, r = 1, int(1e7)\n",
    "        return bisect_left(range(r + 1), 1, l, key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        def help(speed):\n",
    "            n = len(dist)\n",
    "            ans = 0\n",
    "            for i in range(n):\n",
    "                if i != n - 1:\n",
    "                    ans = ans + math.ceil(dist[i]/speed)\n",
    "                else:\n",
    "                    ans = ans + dist[i]/speed\n",
    "            return ans\n",
    "        if len(dist) - 1 >= hour:\n",
    "            return -1\n",
    "        left = 1\n",
    "        right = 10 ** 7\n",
    "        while left < right:\n",
    "            mid = (left + right)//2\n",
    "            if help(mid) > hour:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        if hour <= len(dist) - 1:\n",
    "            return -1\n",
    "        def check(speed):\n",
    "            time = 0\n",
    "            for i in range(len(dist) - 1):\n",
    "                time += math.ceil(dist[i] / speed)\n",
    "            time += dist[-1] / speed\n",
    "            if time <= hour:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        right = 10 ** 7 + 1\n",
    "        left = 0\n",
    "\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                right = mid \n",
    "            else:\n",
    "                left = mid \n",
    "        \n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        def check(v):\n",
    "            sump=0\n",
    "            for i in range(n-1):\n",
    "                sump+=math.ceil(dist[i]/v)\n",
    "            sump+=dist[-1]/v\n",
    "            return sump>hour\n",
    "        left,right,n=1,10**7,len(dist)\n",
    "        if n-1>=hour:\n",
    "            return -1\n",
    "        while left<right:\n",
    "            mid=(left+right)>>1\n",
    "            if check(mid):\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        if hour<=len(dist)-1:\n",
    "            return -1\n",
    "        n=len(dist)\n",
    "        high=max(max(dist),ceil(dist[n-1]/(hour-n+1)))\n",
    "        low=1\n",
    "        while low < high:\n",
    "            mid=(low+high)//2\n",
    "            if sum(ceil(d/mid) for d in dist) - ceil(dist[n-1]/mid) + dist[n-1]/mid <=hour:\n",
    "                high=mid\n",
    "            else:\n",
    "                low=mid+1\n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        # 单调性，二分答案\n",
    "        l,r=1,10**7+1\n",
    "        n=len(dist)\n",
    "        if n-1>=hour:\n",
    "            return -1\n",
    "        def check(mid):\n",
    "            h=0\n",
    "            for i,x in enumerate(dist):\n",
    "                if i==n-1:\n",
    "                    h+=x/mid \n",
    "                else:\n",
    "                    h+=(x+mid-1)//mid \n",
    "            return h<=hour\n",
    "        while l<r:\n",
    "            mid=l+r>>1\n",
    "            if check(mid):\n",
    "                r=mid \n",
    "            else:\n",
    "                l=mid+1\n",
    "        return l \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        def check(ds, v):\n",
    "            if v == 0:\n",
    "                return inf\n",
    "            t = 0\n",
    "            for i, d in enumerate(ds):\n",
    "                dt = d / v\n",
    "                t += dt if i == len(ds) - 1 else ceil(dt)\n",
    "            return t\n",
    "        # print(dist)\n",
    "\n",
    "\n",
    "        L = 1\n",
    "        R = 1 << 31\n",
    "        while L <= R:\n",
    "            mid = (L + R) // 2\n",
    "            t = check(dist, mid)\n",
    "            # print(f'L={L}, R={R}, mid={mid}, t={t}, hour={hour}')\n",
    "            if t > hour:\n",
    "                L = mid+1\n",
    "            elif t <= hour:\n",
    "                R = mid-1\n",
    "        # print(f'R={R}, t={check(dist, R)}')\n",
    "        # print(f'L={L}, t={check(dist, L)}')\n",
    "\n",
    "        return L if check(dist, L) <= hour else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        # max_value 0.01 * dist[-1] 或 max(dist)\n",
    "        def check(self, dist: List[int], hour: float, speed: int):\n",
    "            sum = 0\n",
    "            if len(dist) > 1:\n",
    "                for i in range(0, len(dist) - 1):\n",
    "                    sum += ceil(dist[i] / speed)\n",
    "            sum += dist[-1] / speed\n",
    "            return sum <= hour\n",
    "        intH = hour // 1 # 时间整数部分\n",
    "        minute = hour - intH # 时间小数部分\n",
    "\n",
    "        l = 0\n",
    "        r = max(dist) + 1 if minute == 0.0 else max(max(dist), ceil(dist[-1] / minute)) + 1\n",
    "\n",
    "        # 记录边界，如果超过边界还不满足则无法到达\n",
    "        limit = r\n",
    "        while l + 1 < r:\n",
    "            m = l + (r - l) // 2\n",
    "            if check(self, dist, hour, m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m\n",
    "        return r if r != limit else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        n = len(dist)-1\n",
    "        if hour<=n:\n",
    "            return -1\n",
    "        high=max(max(dist),ceil(dist[-1]/(hour-n)))\n",
    "        low=1\n",
    "        while low < high:\n",
    "            mid=low+high >> 1\n",
    "            if sum(ceil(d/mid) for d in dist) - ceil(dist[-1]/mid) + dist[-1]/mid <=hour:\n",
    "                high=mid\n",
    "            else:\n",
    "                low=mid+1\n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        n = len(dist)\n",
    "        hr = round(hour*100)\n",
    "        if 100 * (n - 1) >= hr:\n",
    "            return -1\n",
    "\n",
    "        def check(speed: int) -> bool:\n",
    "            t = 0\n",
    "            for i in range(n-1):\n",
    "                t += (dist[i] - 1) // speed + 1\n",
    "            t *= speed\n",
    "            t += dist[-1]\n",
    "            return t*100 <= hr * speed\n",
    "        if hour % 1 == 0:\n",
    "            r = max(dist)\n",
    "        else:\n",
    "            r = max(max(dist), int(dist[-1] / (hour % 1))) + 1\n",
    "        l = max(1, int(sum(dist) / hour )) \n",
    "        print(l,r)\n",
    "        while l < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        # n=len(dist)\n",
    "        # hr=round(hour*100)\n",
    "        # if hr<=100*(n-1):\n",
    "        #     return -1\n",
    "        \n",
    "        # def check(speed):\n",
    "        #     t=0\n",
    "        #     for i in range(n-1):\n",
    "        #         t+=(dist[i]-1)//speed + 1\n",
    "        #     t*=speed\n",
    "        #     t+=dist[-1]\n",
    "        #     return t*100<=hr*speed\n",
    "        \n",
    "        # left=1\n",
    "        # right = 10**7\n",
    "        # while left<right:\n",
    "        #     mid=(left+right)//2\n",
    "        #     if check(mid):\n",
    "        #         r=mid\n",
    "        #     else:\n",
    "        #         left=mid+1\n",
    "        # return left\n",
    "\n",
    "        n = len(dist)\n",
    "        hr = round(hour * 100)\n",
    "        # 时间必须要大于路程段数减 1\n",
    "        if hr <= 100 * (n - 1):\n",
    "            return -1\n",
    "        # 判断当前时速是否满足时限\n",
    "        def check(speed: int) -> bool:\n",
    "            t = 0\n",
    "            # 前 n-1 段中第 i 段贡献的时间： floor(dist[i] / mid)\n",
    "            for i in range(n - 1):\n",
    "                t += (dist[i] - 1) // speed + 1\n",
    "            # 最后一段贡献的时间： dist[n-1] / mid\n",
    "            t *= speed\n",
    "            t += dist[-1]\n",
    "            return t * 100 <= hr * speed   # 通分以转化为整数比较\n",
    "        \n",
    "        # 二分\n",
    "        l, r = 1, 10 ** 7\n",
    "        while l < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l   # 满足条件的最小时速\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        n = len(dist)-1\n",
    "        if hour<=n:\n",
    "            return -1\n",
    "        high=max(max(dist),ceil(dist[-1]/(hour-n)))\n",
    "        low=1\n",
    "        while low < high:\n",
    "            mid=(low+high)//2\n",
    "            if sum(ceil(d/mid) for d in dist) - ceil(dist[-1]/mid) + dist[-1]/mid <=hour:\n",
    "                high=mid\n",
    "            else:\n",
    "                low=mid+1\n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:\n",
    "        if len(dist) > ceil(hour):return -1\n",
    "        left, right = 1, max(dist) * 100\n",
    "        while left <= right:\n",
    "            mid = (left + right)//2\n",
    "            total = sum(ceil(d/mid) if i != len(dist) - 1 else (d/mid) for i, d in enumerate(dist))\n",
    "            if total > hour:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid -1\n",
    "        return left "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
